The Great Revegetation¶
长时间的干旱使得Farmer John的N块草地上牧草匮乏。随着雨季即将到来,现在应当是重新种植的时候了。
在Farmer John的储物棚里有四个桶,每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶农,Farmer John想要确保他的每头奶牛都能得到丰富的食谱。他的M头奶牛每一头都有两块喜爱的草地,他想要确保这两块草地种植不同种类的草,从而每头奶牛都可以有两种草可供选择。Farmer John知道没有一块草地受到多于3头奶牛的喜爱。
请帮助Farmer John选择每块草地所种的草的种类,使得所有奶牛的营养需求都得到满足。
输入格式(文件名:revegetate.in):¶
输入的第一行包含N(2 \leq N \leq 100)和M(1 \leq M \leq 150)。以下M行,每行包含两个范围为1 \ldots N的整数,为Farmer John的一头奶牛喜欢的两块草地。
输出格式(文件名:revegetate.out):¶
输出一个N位数,每一位均为1 \ldots 4之一,表示每一块草地上所种的草的种类。第一位对应草地1的草的种类,第二位对应草地2,以此类推。如果有多种可行的解,只需输出所有解中最小的N位数。
输入样例:¶
1 2 3 4 5 6 7 | 5 6
4 1
4 2
4 3
2 5
1 2
1 5
|
输出样例:¶
1 | 12133
|